﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200824
    {
        /// <summary>
        /// 获取最大公共子串，动态规划法
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns></returns>
        public string GetMaxCommonStrByDP(string str1,string str2)
        {
            int[,] dp = new int[str1.Length+1,str2.Length+1];
            int maxLen = 0;
            int maxI = 0;
            StringBuilder res = new StringBuilder();

            for (int i = 0; i < str1.Length+1; i++)
            {
                dp[i, 0] = 0;
            }

            for (int i = 0; i < str2.Length+1; i++)
            {
                dp[0, i] = 0;
            }

            for (int i = 1; i < str1.Length; i++)
            {
                for (int j = 1; j < str2.Length; j++)
                {
                    if (str1[i - 1] == str2[j - 1])
                    {
                        dp[i, j] = dp[i - 1, j - 1] + 1;
                        if (dp[i, j] > maxLen)
                        {
                            maxLen = dp[i, j];
                            maxI = i-1;
                        }
                    }
                    else
                    {
                        dp[i, j] = 0;
                    }
                }
            }

            for (int i = maxI - maxLen + 1; i <=maxI; i++)
            {
                res.Append(str1[i]);
            }
            return res.ToString();
        }
    }
}
